The invention pertains to the maintenance and use of a branch history table in a microprocessor.
Most modern computers, including those that execute instructions out-of-order and/or via a pipelined execution unit, execute instructions xe2x80x9cspeculativelyxe2x80x9d. That is, instructions are executed before the instructions on which they depend have been fully executed, and quite possibly, before the outcomes of branches in the instruction stream are known. To achieve a high degree of performance, the microprocessors in these computers employ a variety of techniques to minimize the cost of erroneously predicted branches in the instruction stream. These techniques usually involve some form of xe2x80x9cbranch predictionxe2x80x9d. Branch prediction is a means of optimizing for the outcome of a branch instruction which is mostly likely to occur (either xe2x80x9ctakenxe2x80x9d or xe2x80x9cnot takenxe2x80x9d).
Typically, a branch prediction will be based on one of two types of information: 1) static prediction information, or 2) dynamic prediction information. Static prediction information is generated prior to the execution of a computer program, and may be based on factors such as instruction type, position in the instruction stream, instruction repetition, and so on. Dynamic prediction information is generated during the execution of a computer program, and usually depends on a history of previous outcomes of a given branch and/or other branch instructions.
Dynamic prediction information is stored in a branch history table comprising a number of entries. If a branch history table was large enough, it is conceivable that a distinct history could be maintained for each branch instruction of a computer program. However, given that microprocessor chip area is a costly resource, and that branch history tables are often scaled back to make room for other important microprocessor elements, entries in a branch history table are often shared. Interference between conflicting branch histories is therefore a significant problem.
When conflicting histories share a single entry in a branch history table, the history for any given branch instruction is often corrupted by other branch instructions, thereby resulting in a mispredicted branch outcome. When a branch outcome is mispredicted, serious and costly consequences result. For example, instruction pipelines may stall, instruction execution units may be halted, caches and registers may need to be flushed, and so on. All of these consequences result in unacceptable delays.
It is therefore a primary object of this invention to provide methods and apparatus which reduce interference in a branch history table of a microprocessor, thereby yielding 1) more accurate branch predictions, and consequently 2) fewer delays caused by erroneously predicted branches.
To understand the invention, it must first be recognized that the vast majority of branches are either xe2x80x9calmost always takenxe2x80x9d or xe2x80x9calmost always not takenxe2x80x9d. These branches may be referred to as xe2x80x9cwell-behavedxe2x80x9d branches. One must also recognize that when the outcome of a branch switches, it often switches from xe2x80x9calmost always takenxe2x80x9d to xe2x80x9calmost always not takenxe2x80x9d, or vice versa. It is also important to note that branch prediction schemes typically rely on the assumption that most branches are well-behaved. As a result, the goal of both static and many dynamic branch prediction schemes is to predict what the dominant outcome of a branch will be.
Recognizing the above facts, one can appreciate that the prediction accuracy of a well-behaved branch of one type (e.g., an xe2x80x9calmost always takenxe2x80x9d branch) is degraded when the branch shares a branch history table entry with a well-behaved branch of the other type (e.g., an xe2x80x9calmost always not takenxe2x80x9d branch).
The branch prediction schemes of the Hewlett-Packard Company PA-8x00 family of microprocessors (e.g., the PA-8000, PA-8200, and PA-8500) presume the above facts on well-behaved branches to be true. Hewlett-Packard Company is based in Palo Alto, Calif., USA, and the PA-8x00 family of microprocessors is described in more detail in Advanced Performance Features of the 64-bit PA-8000 by D. Hunt (Mar. 5, 1995), HP Pumps Up PA-8x00 Family: PA-8200 in 2Q97, PA-8500 in 2Q98 Aim to Grab Performance Lead by L. Gwennap (Oct. 28, 1996), and PA-8500: The Continuing Evolution of the PA-8000 Family by G. Lesartre and D. Hunt (Feb. 23, 1997). These papers are hereby incorporated by reference for all that they disclose.
Compilers which generate code for the PA-8x00 family of microprocessors are capable of encoding a xe2x80x9chintxe2x80x9d in most branch instructions. These hints are a form of static prediction information, and are indication as to whether the compiler believes a given branch will be mostly taken or mostly not-taken. The compiler for the PA-8000 microprocessor is described in more detail in Compiler Optimizations for the PA-8000 by A. Holler. This paper is hereby incorporated by reference for all that it discloses.
In the achievement of the foregoing objects, the inventor has devised methods and apparatus which utilize these compiler generated hints (or any other static prediction information) to insure that two or more well-behaved branches sharing a single entry in a branch history table do not corrupt the history information stored therein. After execution of a branch instruction, an indication as to whether a branch instruction resulted in a branch being taken or not taken is exclusively ORed with the compiler generated hint for the branch instruction, and the result of this exclusive OR is used to update an appropriate entry in the branch history table. Furthermore, the outcome of a branch instruction is predicted in response to the exclusive OR of 1) the compiler generated hint, and 2) dynamic prediction information read from an appropriate entry of the branch history table.
Using the methods and apparatus disclosed herein, two well-behaved branches may share an entry in the branch history table, yet not corrupt the history information stored therein (even when the two well-behaved branches comprise one which is mostly taken, and one which is mostly not taken).
These and other important advantages and objectives of the present invention will be further explained in, or will become apparent from, the accompanying description, drawings and claims.